/*
 * Copyright (c) 2018-2024 北京华恒盛世科技有限公司
 * QUICKPOOL is licensed under Mulan PSL v2.
 * You can use this software according to the terms and conditions of the Mulan PSL v2.
 * You may obtain a copy of Mulan PSL v2 at:
 *     http://license.coscl.org.cn/MulanPSL2
 * THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND,
 * EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT,
 * MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
 * See the Mulan PSL v2 for more details.
*/

/**
 * @file   bitset.c
 * @brief  Defines functions about bitset handling.
 * @note   Use bitset to speed up search element.
 */

#include "list.h"
#include "bitset.h"

static bool_t test_value(BITSET_T *, const int);
static BITSET_T *reset(BITSET_T *, unsigned int);


/**
 * @brief        To make a bitset
 *
 * @param[in]    size             #1: Initialized size of the bitset
 * @param[in]    directFunction   #2: Function pointer to get index
 * @param[in]    inverseFunction  #3: Function pointer to get object
 *
 * @retval       Not NULL      #1: Pointer of the bitset
 * @retval       NULL          #2: Failed to make the bitset
 *
 * @note         errno is set when allocate memory failed.
 */
BITSET_T *
gf_set_make(const int size, int (*directFunction)(void *), void *(*inverseFunction)(int ))
{
    int         sz;
    BITSET_T   *set;

    set = (BITSET_T *)calloc(1, sizeof(BITSET_T));
    if (NULL == set) {
        return NULL;
    }

    /* Size is the number of elements the caller wants
     * to store in the set.
     */
    sz = (size > 0) ? size : SET_DEFAULT_SIZE;

    /* Width is how many bytes we need to store
     * the size number of elements.
     */
    set->width = (sz + WORDLENGTH - 1)/WORDLENGTH;

    set->size = (set->width) * WORDLENGTH;

    set->num_element = 0;

    set->bitmask = (unsigned int *)calloc(set->width, sizeof(unsigned int));
    if (NULL == set->bitmask) {
        return NULL;
    }

    if (directFunction)
        set->get_index = directFunction;
    else
        set->get_index = NULL;

    if (inverseFunction)
        set->get_object = inverseFunction;
    else
        set->get_object = NULL;

    return (set);

} /* gf_set_make */

/**
 * @Brief      Free up the bitset
 *
 * @param[in]  set     #1: bitset to be freed
 *
 * @note       Pointer of function could be NULL
 */
void
gf_set_free(BITSET_T * set)
{
    if (NULL == set) {
        return;
    }

    free(set->bitmask);
    free(set);
    set = NULL;

    return;
} /* gf_set_free */

/**
 * @Brief      Check if the object is in the bitset
 *
 * @param[in]         set     #1: bitset to check
 * @param[in]         obj     #2: object
 *
 * @retval            TRUE    #1: object is in the bitset
 * @retval            FALSE   #2: object is not in the bitset
 *
 * @note       None
 */
bool_t
gf_set_ismember(BITSET_T *set, void *obj)
{
    int *value;
    unsigned int x;

    if (NULL == set) {
        return FALSE;
    }

    if (0 == SET_NUM_ENTS(set)) {
        return FALSE;
    }

    if (set->get_index == NULL) {
        value = (int *)obj;
        x = *value;
    } else {
        x = (*set->get_index)(obj);
        if (x < 0) {
            return FALSE;
        }
    }

    if (x >= set->size)
        return FALSE;

    return test_value(set, x);
} /* gf_set_ismember */

/**
 * @Brief      Install the object to the bitset
 *
 * @param[in|out]  set     #1: bitset to install object
 * @param[in]      obj     #2: object to be installed
 *
 * @retval     -1          #1: Failed to install the object
 * @retval      0          #2: Succeed to install the object
 *
 * @note       None
 */
int
gf_set_install(BITSET_T * set, void *obj)
{
    int *value;
    int word;
    int offset;
    unsigned int x;

    if (NULL == set) {
        return -1;
    }

    if (set->get_index == NULL) {
        value = (int *)obj;
        x = *value;
    } else {
        x = (*set->get_index)(obj);
        if (x < 0) {
            return -1;
        }
    }

    if (x >= set->size) {
        reset(set, x);
        if (set == NULL)
            return -1;
    }

    if (test_value(set, x) == TRUE) {
        return -1;
    }

    word = SET_GET_WORD(x);
    offset = SET_GET_BIT_IN_WORD(x);

    *(set->bitmask + word) |= (SET_BIT_ON << offset);

    set->num_element++;

    return 0;
} /* gf_set_install */

/**
 * @Brief      Remove the object from the bitset
 *
 * @param[in|out]  set     #1: bitset to remove object
 * @param[in]      obj     #2: object to be removed
 *
 * @retval     -1          #1: Failed to remove the object
 * @retval      0          #2: Succeed to remove the object
 *
 * @note       None
 */
int
gf_set_remove(BITSET_T * set, void *obj)
{
    int *value;
    int word;
    int offset;
    unsigned int x;

    if (NULL == set) {
        return -1;
    }

    if (0 == SET_NUM_ENTS(set)) {
        return -1;
    }

    if (set->get_index == NULL) {
        value = (int *)obj;
        x = *value;
    } else {
        x = set->get_index(obj);
        if (value < 0) {
            return -1;
        }
    }

    if (x >= set->size)
        return FALSE;

    word = SET_GET_WORD(x);
    offset = SET_GET_BIT_IN_WORD(x);

    *(set->bitmask + word) &= ~(SET_BIT_ON << offset);

    set->num_element--;

    return 0;
} /* gf_set_remove */

/**
 * @Brief      Clear the bitmask of the bitset
 *
 * @param[in|out]  set     #1: bitset to be cleared
 *
 * @note       None
 */
void
gf_set_clear(BITSET_T * set)
{

    if (NULL == set) {
        return;
    }

    memset(set->bitmask, 0, set->width*sizeof(unsigned int));

    set->num_element=0;

    return;
} /* gf_set_clear */


/**
 * @brief      Enlarge the size of the bitset.
 *
 * @param[in|out]  set      #1: the bitset
 * @param[in]      size     #2: the new size of the bitset
 *
 * @note       We create a new bitset and copy the element from old bitset to the new one.
 */
static BITSET_T *
reset(BITSET_T *set, unsigned int size)
{
    unsigned int width;

    width = set->width;
    set->width += size + SET_WORD_DEFAULT_EXTENT;

    set->bitmask = (unsigned int *)
        realloc(set->bitmask, sizeof(unsigned int)*set->width);
    if (set->bitmask == NULL) {
        return NULL;
    }

    memset(set->bitmask + width, 0,
           sizeof(unsigned int)*(set->width - width));

    set->size = (set->width)*WORDLENGTH;

    return (set);
} /* reset */

/**
 * @Brief      Test if a bitset in the bitmask.
 *
 * @param[in]      set     #1: bitset to remove object
 * @param[in]      obj     #2: object to be removed
 *
 * @retval         TRUE    #1: in
 * @retval         FALSE   #2: not in
 *
 * @note       None
 */
static bool_t
test_value(BITSET_T *set, const int value)
{
    int      word;
    int      offset;
    bool_t   trueORfalse;

    word = SET_GET_WORD(value);

    offset = SET_GET_BIT_IN_WORD(value);

    trueORfalse = ((*(set->bitmask + word) & (SET_BIT_ON << offset)) != 0);

    return trueORfalse;
} /* test_value */
